package month1;

import java.util.Deque;
import java.util.LinkedList;

//42.接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
public class TrapRainWater42_02 {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(trap1(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    /**
     * 单调栈
     * @param height 雨水数组
     * @return 最多的雨水
     */
    static int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int ret = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int pre = stack.pop();
                if(stack.isEmpty()) {
                    break;
                }
                int dist = i - stack.peek() - 1;
                ret += (Math.min(height[i], height[stack.peek()]) - height[pre]) * dist;
            }
            stack.push(i);
        }
        return ret;
    }

    /**
     * 双指针动态规划
     * @param height 雨水数组
     * @return 最多的雨水
     */
    static int trap1(int[] height) {
      int ret = 0;
      int l = 0, r = height.length - 1, lMax = 0, rMax = 0;
        while (l < r) {
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if (height[l] < height[r]) {
                ret += lMax - height[l++];
            } else {
                ret += rMax - height[r--];
            }
        }
        return  ret;
    }
}
